package com.shm.leetcode;

import java.util.ArrayList;

/**
 * 109. 有序链表转换二叉搜索树
 * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 *
 * 示例:
 *
 * 给定的有序链表： [-10, -3, 0, 5, 9],
 *
 * 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
 *
 *       0
 *      / \
 *    -3   9
 *    /   /
 *  -10  5
 * @author SHM
 */
public class SortedListToBST {
    public TreeNode sortedListToBST_0(ListNode head) {
        ListNode node = head;
        ArrayList<Integer> list = new ArrayList<>();
        while (node != null){
            list.add(node.val);
            node = node.next;
        }
        int start = 0;
        int end = list.size()-1;
        return buildTree(list,start,end);
    }

    public TreeNode buildTree(ArrayList<Integer> list,int start,int end){
        if(start>end){
            return null;
        }
        int mid = getMid(start, end);
        TreeNode node = new TreeNode();
        node.left = buildTree(list,start,mid-1);
        node.val = list.get(mid);
        node.right = buildTree(list,mid+1,end);
        return node;
    }
    public int getMid(int start,int end){
        return (start+end+1)/2;
    }

    /**
     * 前言
     * 将给定的有序链表转换为二叉搜索树的第一步是确定根节点。由于我们需要构造出平衡的二叉树，因此比较直观的想法是让根节点左子树中的节点个数与右子树中的节点个数尽可能接近。这样一来，左右子树的高度也会非常接近，可以达到高度差绝对值不超过 11 的题目要求。
     *
     * 如何找出这样的一个根节点呢？我们可以找出链表元素的中位数作为根节点的值。
     *
     * 这里对于中位数的定义为：如果链表中的元素个数为奇数，那么唯一的中间值为中位数；如果元素个数为偶数，那么唯二的中间值都可以作为中位数，而不是常规定义中二者的平均值。
     *
     * 根据中位数的性质，链表中小于中位数的元素个数与大于中位数的元素个数要么相等，要么相差 11。此时，小于中位数的元素组成了左子树，大于中位数的元素组成了右子树，它们分别对应着有序链表中连续的一段。在这之后，我们使用分治的思想，继续递归地对左右子树进行构造，找出对应的中位数作为根节点，以此类推。
     *
     * 可以证明，这样的构造方法得到的二叉搜索树是平衡的，详见文末的「正确性证明」部分。
     *
     * 方法一：分治
     * 我们可以直接模拟「前言」部分的构造方案。
     *
     * 具体地，设当前链表的左端点为 \textit{left}left，右端点 \textit{right}right，包含关系为「左闭右开」，即 \textit{left}left 包含在链表中而 \textit{right}right 不包含在链表中。我们希望快速地找出链表的中位数节点 \textit{mid}mid。
     *
     * 为什么要设定「左闭右开」的关系？由于题目中给定的链表为单向链表，访问后继元素十分容易，但无法直接访问前驱元素。因此在找出链表的中位数节点 \textit{mid}mid 之后，如果设定「左闭右开」的关系，我们就可以直接用 (\textit{left}, \textit{mid})(left,mid) 以及 (\textit{mid}.\textit{next}, \textit{right})(mid.next,right) 来表示左右子树对应的列表了。并且，初始的列表也可以用 (\textit{head}, \textit{null})(head,null) 方便地进行表示，其中 \textit{null}null 表示空节点。
     *
     * 找出链表中位数节点的方法多种多样，其中较为简单的一种是「快慢指针法」。初始时，快指针 \textit{fast}fast 和慢指针 \textit{slow}slow 均指向链表的左端点 \textit{left}left。我们将快指针 \textit{fast}fast 向右移动两次的同时，将慢指针 \textit{slow}slow 向右移动一次，直到快指针到达边界（即快指针到达右端点或快指针的下一个节点是右端点）。此时，慢指针对应的元素就是中位数。
     *
     * 在找出了中位数节点之后，我们将其作为当前根节点的元素，并递归地构造其左侧部分的链表对应的左子树，以及右侧部分的链表对应的右子树。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)，其中 nn 是链表的长度。
     *
     * 设长度为 nn 的链表构造二叉搜索树的时间为 T(n)T(n)，递推式为 T(n) = 2 \cdot T(n/2) + O(n)T(n)=2⋅T(n/2)+O(n)，根据主定理，T(n) = O(n \log n)T(n)=O(nlogn)。
     *
     * 空间复杂度：O(\log n)O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(\log n)O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }

    public TreeNode buildTree(ListNode left,ListNode right){
        if(left==right){
            return null;
        }
        ListNode mid = getMid(left, right);
        TreeNode node = new TreeNode(mid.val);
        node.left = buildTree(left,mid);
        node.right = buildTree(mid.next,right);
        return node;
    }
    public ListNode getMid(ListNode left,ListNode right){
        ListNode slow = left;
        ListNode fast = left;
        while(fast!=right&&fast.next!=right){
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    ListNode globalHead;

    /**
     * 方法二：分治 + 中序遍历优化
     * 方法一的时间复杂度的瓶颈在于寻找中位数节点。由于构造出的二叉搜索树的中序遍历结果就是链表本身，因此我们可以将分治和中序遍历结合起来，减少时间复杂度。
     *
     * 具体地，设当前链表的左端点编号为 \textit{left}left，右端点编号为 \textit{right}right，包含关系为「双闭」，即 \textit{left}left 和 \textit{right}right 均包含在链表中。链表节点的编号为 [0, n)[0,n)。中序遍历的顺序是「左子树 - 根节点 - 右子树」，那么在分治的过程中，我们不用急着找出链表的中位数节点，而是使用一个占位节点，等到中序遍历到该节点时，再填充它的值。
     *
     * 我们可以通过计算编号范围来进行中序遍历：
     *
     * 中位数节点对应的编号为 \textit{mid} = (\textit{left} + \textit{right} + 1) / 2mid=(left+right+1)/2；
     *
     * 根据方法一中对于中位数的定义，编号为 (\textit{left} + \textit{right}) / 2(left+right)/2 的节点同样也可以是中位数节点。
     *
     * 左右子树对应的编号范围分别为 [\textit{left}, \textit{mid}-1][left,mid−1] 和 [\textit{mid}+1, \textit{right}][mid+1,right]。
     *
     * 如果 \textit{left} > \textit{right}left>right，那么遍历到的位置对应着一个空节点，否则对应着二叉搜索树中的一个节点。
     *
     * 这样一来，我们其实已经知道了这棵二叉搜索树的结构，并且题目给定了它的中序遍历结果，那么我们只要对其进行中序遍历，就可以还原出整棵二叉搜索树了。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是链表的长度。
     *
     * 设长度为 nn 的链表构造二叉搜索树的时间为 T(n)T(n)，递推式为 T(n) = 2 \cdot T(n/2) + O(1)T(n)=2⋅T(n/2)+O(1)，根据主定理，T(n) = O(n)T(n)=O(n)。
     *
     * 空间复杂度：O(\log n)O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(\log n)O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/
     *
     * @param head
     * @return
     */
    public TreeNode sortedListToBST_1(ListNode head) {
        globalHead = head;
        int len = getLength(head);
        return buildTree(0,len-1);
    }

    public TreeNode buildTree(int left,int right){
        if(left>right){
            return null;
        }
        //这样求mid是为了保证当链表长度为偶数时，根节点的值等于靠后的那个中位数
        int mid = (left+right+1)/2;
        TreeNode node = new TreeNode();
        node.left = buildTree(left,mid-1);
        node.val = globalHead.val;
        globalHead = globalHead.next;
        node.right = buildTree(mid+1,right);
        return node;
    }
    public int getLength(ListNode head){
        int res = 0;
        while(head!=null){
            res++;
            head=head.next;
        }
        return res;
    }



//    public TreeNode sortedListToBST(ListNode head) {
//        ListNode node = head;
//        ArrayList<Integer> list = new ArrayList<>();
//        while (node != null){
//            list.add(node.val);
//            node = node.next;
//        }
//        int start = 0;
//        int end = list.size();
//        return buildTree(list,start,end);
//    }
//
//    public TreeNode buildTree(ArrayList<Integer> list,int start,int end){
//        if(start>=end){
//            return null;
//        }
//        int mid = getMid(start, end);
//        TreeNode node = new TreeNode();
//        node.left = buildTree(list,start,mid);
//        node.val = list.get(mid);
//        node.right = buildTree(list,mid+1,end);
//        return node;
//    }
//    public int getMid(int start,int end){
//        return start+(end-start)/2;
//        return (start+end)/2;
//    }

    public TreeNode sortedListToBST_3(ListNode head) {
        //边界条件的判断
        if (head == null){
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        //这里通过快慢指针找到链表的中间结点slow，pre就是中间
        //结点slow的前一个结点
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //链表断开为两部分，一部分是node的左子节点，一部分是node
        //的右子节点
        pre.next = null;
        //node就是当前节点
        TreeNode node = new TreeNode(slow.val);
        //从head节点到pre节点是node左子树的节点
        node.left = sortedListToBST(head);
        //从slow.next到链表的末尾是node的右子树的结点
        node.right = sortedListToBST(slow.next);
        return node;
    }

//    作者：sdwwld
//    链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/kuai-man-zhi-zhen-jie-jue-ji-bai-liao-100de-yong-h/
}
